import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int n;
    int k;
    public List<List<Integer>> combinationSum3(int _k, int _n) {
        k = _k;
        n = _n;
        dfs(1);
        return ret;
    }

    private void dfs(int pos) {
        if(path.size() == k) {
            //判断当前组合之和是否为n
            int tmp = 0;
            for (Integer integer : path) {
                tmp += integer;
            }
            if(tmp != n) return;
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = pos; i <= 9; i++){
            path.add(i);
            dfs(i + 1);
            //恢复现场
            path.remove(path.size() - 1);
        }
    }
}